public class Main {


    public ListNode copyList(ListNode head, int k) {
        ListNode res = new ListNode(0);
        ListNode rr = res;
        for (int i = 0; i < k; i++) {
            ListNode s = head;
            while (s != null) {
                rr.next = new ListNode(s.val);
                s = s.next;
                rr = rr.next;
            }
        }

        return res.next;
    }

    public String longestCommonStr(String str1, String str2) {
        String res = "";
        for (int i = 0; i < str1.length(); i++) {
            for (int j = i; j <= str1.length(); j++) {
                String substring = str1.substring(i, j);
                if (str2.contains(substring) && substring.length() >= res.length()) {
                    res = substring;
                }
            }
        }

        return res;
    }

    public static void main(String[] args) {
        Main m = new Main();
//        ListNode n1 = new ListNode(2);
//        ListNode n2 = new ListNode(3);
//        ListNode n3 = new ListNode(4);
//
//        n1.next = n2;
//        n2.next = n3;
//
//        ListNode r = m.copyList(n1, 3);
//        while (r != null) {
//            System.out.print(r.val + " ");
//            r = r.next;
//        }
//        System.out.println(r);
        System.out.println(m.longestCommonStr("hello word","hallo wood"));
    }
}

class ListNode {
    int val;
    ListNode next = null;

    public ListNode(int val) {
        this.val = val;
    }
}
